/**
 * 474. 一和零
 * https://leetcode-cn.com/problems/ones-and-zeroes/
 */
public class Solutions_474 {
    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;  // output: 4

//        String[] strs = {"10", "0", "1"};
//        int m = 1, n = 1;  // output: 2

        int result = findMaxForm(strs, m, n);
        System.out.println(result);
    }

    public static int findMaxForm(String[] strs, int m, int n) {
        // dp[5][3] = 4，表示 5 个 0，3 个 1 的情况下，子集最大为 4
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            // 获取到 str 中 "0" 和 "1" 的数量
            int[] counts = getZeroOneCount(str);
            int zero = counts[0], one = counts[1];

            // 逆序填充 dp 矩阵
            // 动态转移方程：dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--) {
                    int max = dp[i - zero][j - one] + 1;
                    if (max > dp[i][j]) {
                        dp[i][j] = max;
                    }
                }
            }
        }
        return dp[m][n];
    }

    public static int[] getZeroOneCount(String str) {
        int[] counts = new int[2];
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                counts[0] ++;
            } else {
                counts[1] ++;
            }
        }
        return counts;
    }
}
